package salb1;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;

import nsga.Individual;
import salb1.Helper;

import common.GeneticOperations;



public class Salb1GeneticOperations implements GeneticOperations<Salb1Genotype> {

	private final double MOVE_PROBABILITY = 0.1; // szansa że z danej grupy zostaną przeniesione operacje do innej
	private final int MAX_TO_MOVE = 2; // maksymalna ilość operacji które można przeniść

	private TimeOfOperations too;

	public Salb1GeneticOperations(TimeOfOperations too) {
		this.too = too;
	}

	/**
	 * Na razie jest tak biora jedna grupa z jednego rodzica i przenosza w wybrane miejsce do
	 * kopii drugiego rodzica. Usuwam z tej kopii te operacje ktore sie powtarzaja no i mamy
	 * nowego osobnika.
	 */
	public List<Salb1Genotype> crossover2(Salb1Genotype g1, Salb1Genotype g2) {

		Random rand = new Random();
		Salb1Genotype child = new Salb1Genotype(g2);

		assert checkGenotype(g1);
		assert checkGenotype(g2);
		assert checkGenotype(child);

		List<Integer> movedGroup = g1.getGroups().get(rand.nextInt(g1.getGroups().size()));
		movedGroup = new LinkedList<Integer>(movedGroup);

		// usuwam te z grupy ktore przenosza
		for (Integer operationToRemove : movedGroup) {
			for (List<Integer> existingGroup : child.getGroups()) {
				existingGroup.remove(operationToRemove);
			}
		}
		// sprawdzam ktora grupa ma najmniej operacji (ja usune)
		List<Integer> leastNumerousGroup = child.getGroups().get(0);
		for (List<Integer> existingGroup : child.getGroups()) {
			if (existingGroup.size() < leastNumerousGroup.size()) {
				leastNumerousGroup = existingGroup;
			}
		}
		int leastNumerousIndex = child.getGroups().indexOf(leastNumerousGroup);
		child.getGroups().remove(leastNumerousGroup);
		child.getGroups().add(leastNumerousIndex, movedGroup);

		// trza cos zrobic z tymi operacjami 
		for (Integer operation : leastNumerousGroup) {
			List<Integer> newGroup = child.getGroups().get(rand.nextInt(child.getGroups().size()));
			newGroup.add(operation);
		}
		// return child
		assert checkGenotype(g1);
		assert checkGenotype(g2);
		assert checkGenotype(child);

		List<Salb1Genotype> result = new LinkedList<Salb1Genotype>();
		result.add(child);
		return result;
	}

	/**
	 * Krzyżowanie jednopunktowe.<br>
	 * Losuje punkt. Część genotypu od 0 do punktu, lub od punktu
	 * do końca zostawiam z pierwszego rodzica, a reszta daję z drugiego.
	 * Część z pierwszego rodzica nie jest potem zmieniana, dzięki temu 
	 * kawałek z jednego z rodziców zawsze jest w potomku.
	 */
	public List<Salb1Genotype> crossover(Salb1Genotype g1, Salb1Genotype g2) {

		Random rand = new Random();

		int numOfGroups = g1.getNumOfStations();
		int point = rand.nextInt(numOfGroups);

		// losuje czy pierwsza czy druga część, TODO: zaimplementować bez głupiego odwracania
		boolean chooseFirstPart = rand.nextBoolean();

		Salb1Genotype child = new Salb1Genotype(g1);

		List<List<Integer>> childGroups = child.getGroups();
		List<List<Integer>> otherParentsGroups = new LinkedList<List<Integer>>(g2.getGroups());
		if (! chooseFirstPart) {
			Collections.reverse(otherParentsGroups);
			Collections.reverse(childGroups);
		}

		List<List<Integer>> firstPartOfChild = new LinkedList<List<Integer>>(childGroups.subList(0, point));
		List<List<Integer>> secondPartOfChild = childGroups.subList(point, childGroups.size());
		secondPartOfChild.clear();

		List<List<Integer>> secondPartOfOtherParent = Helper.deepCopyGroups(otherParentsGroups.subList(point, otherParentsGroups.size()));
		//System.out.println("ilosc genow w dzecku "+childGroups.size());
		childGroups.addAll(secondPartOfOtherParent);
		//System.out.println("ilosc genow w dzecku "+childGroups.size());
		secondPartOfChild = childGroups.subList(point, childGroups.size());
		//System.out.println("secondPartChild "+secondPartOfChild.size());

		// usuwam z drugiej części te co są w pierwszej
		for (List<Integer> firstPartGroup : firstPartOfChild) {
			for (Integer firstPartOperation : firstPartGroup) {
				for (List<Integer> secondPartGroup : secondPartOfChild){
					secondPartGroup.remove(firstPartOperation);
				}
			}
		}

		// spawdzam czy brakuje jakiś operacji w genotypie
		List<Integer> missingOperations = new LinkedList<Integer>();
		for (int operation = 0; operation < g1.getNumOfOperations(); operation++) {
			missingOperations.add(operation);
		}
		for (List<Integer> group : childGroups) {
			missingOperations.removeAll(group);
		}

		// dodaje brakujące losowo do drugiej części potomka
		for (Integer operation : missingOperations) {
			List<Integer> secondPartGroup = secondPartOfChild.get(rand.nextInt(secondPartOfChild.size()));
			secondPartGroup.add(operation);
		}

		if (! chooseFirstPart) {
			Collections.reverse(childGroups);
		}

		/*
	    System.out.println("point: "+point);
	    System.out.println("Parent1: "+g1);
	    System.out.println("Child:   "+child);
	    System.out.println("Parent2: "+g2);
		 */

		assert checkGenotype(child);
		assert checkGenotype(g1);
		assert checkGenotype(g2);

		List<Salb1Genotype> result = new LinkedList<Salb1Genotype>();
		result.add(child);
		return result;

	}

	/**
	 * Skalowanie żeby wszystkie objectives były mniej więcej w tym samym przedziale.
	 */
	public List<Double> getFitnessesFromValue(List<Double> values) {
	    
	    List<Double> result = new ArrayList<Double>(2);
	    result.add(values.get(0) - 5);
	    result.add( (values.get(1) / 200.0) );
	    return result;
	}

	public List<Double> getValues(Salb1Genotype genotype) {

		int [][] T_vs = new int[too.getNumOfVariants()][too.getNumOfStations()];
		for (int stationNum = 0; stationNum < too.getNumOfStations(); stationNum++) {
			for (int variantNum = 0; variantNum < too.getNumOfVariants(); variantNum++) {

				int time = 0;
				for (int operationNum : genotype.getOperationsForStation(stationNum)) {
					time += too.getTimeOf(operationNum,variantNum);
				}
				T_vs[variantNum][stationNum] = time;
			}
		}
		//System.out.println("T_vs "+T_vs.length);

		double[] T_s = new double[too.getNumOfStations()];
		for (int s = 0; s < too.getNumOfStations(); s++) {
			double sum = 0;
			for (int v = 0; v < too.getNumOfVariants(); v++) {
				sum += T_vs[v][s];
			}
			T_s[s] = sum / too.getNumOfVariants();
		}

		double T = 0;
		for (int s = 0; s < too.getNumOfStations(); s++) {
			T += T_s[s];
		}
		T /= too.getNumOfStations();

		// standard deviation of station s
		double[] st_dev_s = new double[too.getNumOfStations()];
		for (int s = 0; s < too.getNumOfStations(); s++) {
			double sum = 0;
			for (int v = 0; v < too.getNumOfVariants(); v++) {
				sum += Math.pow(T_vs[v][s] - T_s[s], 2);
			}
			sum /= too.getNumOfVariants();
			st_dev_s[s] = Math.sqrt(sum);
		}

		// objective1 - standard deviation
		double st_dev = 0.0;
		for (int s = 0; s < too.getNumOfStations(); s++) {
			st_dev += st_dev_s[s];
		}
		st_dev /= too.getNumOfStations();

		// objective2 - imbalance
		double imb = 0.0;
		for (int s = 0; s < too.getNumOfStations(); s++) {
			imb += Math.pow(T_s[s]-T, 2);
		}
		imb /= T;

		List<Double> result = new ArrayList<Double>(2);
		result.add(st_dev);
		result.add(imb);

		//System.out.println("St_dev = "+st_dev);
		//System.out.println("Imb = "+imb);

		return result;
	}

	/**
	 * Przenoszenie z jednej grupy kilka operacji do losowej innej grupy.
	 * W pdfie jest rowniez inna propozycja mutacji.
	 */
	public void mutate(Salb1Genotype genotype) {

		//System.out.println();
		//System.out.println("Genotyp przed: "+genotype);

		Random rand = new Random();
		List<List<Integer>> groups = genotype.getGroups();

		for (List<Integer> group : groups)  {
			if (rand.nextDouble() < MOVE_PROBABILITY) {
				if (group.size() > 0) {
					int toMoveNum = Math.min(rand.nextInt(MAX_TO_MOVE), group.size());
					List<Integer> targetGroup = groups.get(rand.nextInt(groups.size())); // may go to the same

					for (int i=0; i<toMoveNum; i++) {
						Integer operation = group.remove(rand.nextInt(group.size()));
						targetGroup.add(operation);		        
					}
				}
			}
		}
		assert checkGenotype(genotype);	
		//System.out.println("Genotyp  po  : "+genotype);
	}

	public Salb1Genotype createRandomGenotype() {

		Random rand = new Random();
		Salb1Genotype genotype = new Salb1Genotype(too.getNumOfStations(),too.getNumOfOperations());

		for (int operationNum = 0; operationNum < too.getNumOfOperations(); operationNum++) {  
			int machineNum = rand.nextInt(too.getNumOfStations());
			genotype.getOperationsForStation(machineNum).add(operationNum);
		}
		assert checkGenotype(genotype);
		return genotype;
	}
	
	@Override
	public Salb1Genotype duplicateGenotype(Salb1Genotype genotype) {
	    return new Salb1Genotype(genotype);
	}

	/*
	 * Funkcje dodane w celu znalezienia wszystkich optymalnych rozwiazan.
	 * Pelny przeglad 
	 */
	public List<Individual<Salb1Genotype>> createAllResults() {
	    
	    long startTime = System.currentTimeMillis();
		
		Salb1Genotype genotype;
		//ArrayList<Salb1Genotype> genList = new ArrayList<Salb1Genotype>();
		Individual<Salb1Genotype> ind;
		List<Individual<Salb1Genotype>> indList = new ArrayList<Individual<Salb1Genotype>>(1);
		List<Individual<Salb1Genotype>> indList2 = new ArrayList<Individual<Salb1Genotype>>(1);

		int w[] = new int[too.getNumOfOperations()];
		int skok[] = new int[too.getNumOfOperations()];
		int m = 0;
		
		long ile = 0;
		long all = (long)Math.pow(too.getNumOfStations(),too.getNumOfOperations());
		System.out.println("ilosc operacji  "+too.getNumOfOperations());
		System.out.println("ilosc stacji    "+too.getNumOfStations());
		System.out.println("ilosc wariantow "+too.getNumOfVariants());
		System.out.println("all "+all);

		for(int i = 0; i < too.getNumOfOperations(); i++) {
			w[i] = 0;
			skok[i] = 1;
		}

		//System.out.println(too.getNumOfOperations());
		final int CYCLE = 100000;
		long begMili = System.currentTimeMillis();
		int j;
		do {
			genotype = new Salb1Genotype(too.getNumOfStations(),too.getNumOfOperations());

			for(int i = 0; i < too.getNumOfOperations(); i++) {
				//System.out.print(w[i]);
				genotype.getOperationsForStation(w[i]).add(i);
			}
			//System.out.println();

			ile++;
			if ((ile % CYCLE) == 0) {
			    long nowMili = System.currentTimeMillis();
			    long toDoCycles = (all - ile) / CYCLE;
			    long timeOfCycle = nowMili - begMili;
			    begMili = nowMili;
			    double percent = ((double)ile) / all;
			    long timeRemaining = toDoCycles * timeOfCycle;
			    System.out.println("wykonalem "+percent+", czas cyklu "+(timeOfCycle)+" msek., zostalo "+(timeRemaining/1000.0/60.0)+" min.");
			}

			m++;
			j = index(m, too.getNumOfStations());
			if(j < too.getNumOfOperations()) {
				w[j] += skok[j];
				if(w[j] == 0) skok[j] = 1;
				if(w[j] == (too.getNumOfStations() - 1)) skok[j] = -1;
			}
			
			ind = new Individual<Salb1Genotype>(genotype, this);

			//jesli zaden z istniejacych nie dominuje, to nowy jest dodawany
			int d = 0;
			for(Individual<Salb1Genotype> indTmp: indList) {
				if(indTmp.checkDomination(ind) == -1)
					break;
				d++;
			}

			if(d == indList.size())
				indList.add(ind);

			//jesli nowy dominuje istniejace, sa one wyrzucane
			for(Individual<Salb1Genotype> indTmp: indList) {
				if(ind.checkDomination(indTmp) != -1)
					indList2.add(indTmp);
			}
			indList.clear();
			indList.addAll(indList2);
			indList2.clear();

			//System.out.println("Rozmiar obecnej populacji " + indList.size());

		} while(j < too.getNumOfOperations());
		
		long stopTime = System.currentTimeMillis();

		System.out.println("Ile " + ile);
		System.out.println("All " + all);
		System.out.println("Jest ostatecznie w koncowej populacji osobnikow: " + indList.size());
		System.out.println("Obliczanie trwalo "+((stopTime-startTime)/1000)+" sek.");
		return indList;
	}
	/*
	 * Funkcje dodane w celu znalezienia wszystkich optymalnych rozwiazan.
	 * Pelny przeglad. Zaczyna od podanej iteracji. I wczytuje osobników z
	 * pliku.
	 */
	public List<Individual<Salb1Genotype>> createAllResults(List<Individual<Salb1Genotype>> aBestList, long begIt, long numOfIt) {
	    	    
	    Salb1Genotype genotype;
	    Individual<Salb1Genotype> ind;
	    
	    if (aBestList == null) {
	        aBestList = new ArrayList<Individual<Salb1Genotype>>();
	    }
	    List<Individual<Salb1Genotype>> bestList = new ArrayList<Individual<Salb1Genotype>>(aBestList);
	    List<Individual<Salb1Genotype>> indList2 = new ArrayList<Individual<Salb1Genotype>>(1);
	    
	    int w[] = new int[too.getNumOfOperations()];
	    	    
	    long begItCopy = begIt;
	    int pos = 0;
	    while(begItCopy != 0) {
	        w[pos] = (int)begItCopy % too.getNumOfStations();
	        begItCopy /= too.getNumOfStations();
	        pos++;
	    }
	      
	    long it = 0;
	    
	    loop:
	    while(it < numOfIt) {
	        
	        genotype = new Salb1Genotype(too.getNumOfStations(),too.getNumOfOperations());
	        
	        for(int i = 0; i < too.getNumOfOperations(); i++) {
	            //System.out.print(w[i]);
	            genotype.getOperationsForStation(w[i]).add(i);
	        }
	        //System.out.println();
	        
	        // nastepne
	        w[0]++;
	        for (int i=0; i<too.getNumOfOperations(); i++) {
	            if (w[i]==too.getNumOfStations()) {
	                w[i] = 0;
	                
	                if ((i+1) == too.getNumOfOperations()) {
	                    break loop;
	                }
	                w[i+1]++;
	            }
	        }
	        
	        it++;
	        	        
	        ind = new Individual<Salb1Genotype>(genotype, this);
	        
	        //jesli zaden z istniejacych nie dominuje, to nowy jest dodawany
	        int d = 0;
	        for(Individual<Salb1Genotype> indTmp: bestList) {
	            if(indTmp.checkDomination(ind) == -1)
	                break;
	            d++;
	        }
	        
	        if(d == bestList.size())
	            bestList.add(ind);
	        
	        //jesli nowy dominuje istniejace, sa one wyrzucane
	        for(Individual<Salb1Genotype> indTmp: bestList) {
	            if(ind.checkDomination(indTmp) != -1)
	                indList2.add(indTmp);
	        }
	        bestList.clear();
	        bestList.addAll(indList2);
	        indList2.clear();
	    }
	    
	    return bestList;
	}

	private int index(int m, int n) {
		int i = 0;
		while((m % n) == 0) {
			i++;
			m = m / n;
		}
		return i;
	}
	
	/**
	 * Sprawdza czy genotyp jest ok
	 */
	private boolean checkGenotype(Salb1Genotype g) {

	    //System.out.println("Sprawdzam genotyp");
	    if (g.getGroups().size() != g.getNumOfStations()) {
	        return false;
	    }

	    List<Integer> allOperations = new LinkedList<Integer>();
	    for (int operationNum = 0; operationNum < g.getNumOfOperations(); operationNum++) {
	        allOperations.add(new Integer(operationNum));
	    }

	    for (List<Integer> group : g.getGroups()) {
	        for (Integer operation : group) {
	            allOperations.remove(operation);
	        }
	    }
	    if (allOperations.size() != 0) {
	        return false;
	    }
	    return true;
	}

    @Override
    public Salb1Genotype createGenotypeFromString(String genotype) {
        
        return new Salb1Genotype(genotype);
    }

}
